翻訳と辞書 Words near each other ・ Tree breeding ・ Tree Canada ・ Tree Care Industry Association ・ Tree Carr ・ Tree City USA ・ Tree Climbers ・ Tree climbing ・ Tree Colored See ・ Tree conservation areas in Singapore ・ Tree Cornered Tweety ・ Tree Council of Ireland ・ Tree credits ・ Tree cricket ・ Tree crop ・ Tree crown measurement ・ Tree decomposition ・ Tree diagram ・ Tree diagram (probability theory) ・ Tree Dtella Gecko ・ Tree Dzhamal ・ Tree farm ・ Tree for Two ・ Tree fork ・ Tree Fort Angst ・ Tree frog ・ Tree Fu Tom ・ Tree Girl ・ Tree girth measurement ・ Tree health ・ Tree height measurement Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Tree decomposition ： ウィキペディア英語版 Tree decomposition In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. In machine learning, tree decompositions are also called junction trees, clique trees, or join trees; they play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. The concept of tree decompositions was originally introduced by . Later it was rediscovered by and has since been studied by many other authors.〔 pp.354–355〕 ==Definition== Intuitively, a tree decomposition represents the vertices of a given graph ''G'' as subtrees of a tree, in such a way that vertices in the given graph are adjacent only when the corresponding subtrees intersect. Thus, ''G'' forms a subgraph of the intersection graph of the subtrees. The full intersection graph is a chordal graph. Each subtree associates a graph vertex with a set of tree nodes. To define this formally, we represent each tree node as the set of vertices associated with it. Thus, given a graph ''G'' = (''V'', ''E''), a tree decomposition is a pair (''X'', ''T''), where ''X'' = is a family of subsets of ''V'', and ''T'' is a tree whose nodes are the subsets ''X''''i'', satisfying the following properties:〔 section 12.3〕 # The union of all sets ''X''''i'' equals ''V''. That is, each graph vertex is associated with at least one tree node. # For every edge (''v'', ''w'') in the graph, there is a subset ''X''''i'' that contains both ''v'' and ''w''. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common. # If ''X''''i'' and ''X''''j'' both contain a vertex ''v'', then all nodes ''X''''k'' of the tree in the (unique) path between ''X''''i'' and ''X''''j'' contain ''v'' as well. That is, the nodes associated with vertex ''v'' form a connected subset of ''T''. This is also known as coherence, or the ''running intersection property''. It can be stated equivalently that if $X\_i$, $X\_j$ and $X\_k$ are nodes, and $X\_k$ is on the path from $X\_i$ to $X\_j$, then $X\_i\; \backslash cap\; X\_j\; \backslash subseteq\; X\_k$. The tree decomposition of a graph is far from unique; for example, a trivial tree decomposition contains all vertices of the graph in its single root node. A tree decomposition in which the underlying tree is a path graph is called a path decomposition, and the width parameter derived from these special types of tree decompositions is known as pathwidth. A tree decomposition (''X'', ''T'' = (''I'', ''F'')) of treewidth ''k'' is ''smooth'', if for all $i\; \backslash in\; I\; :\; |X\_i|\; =\; k\; +\; 1$, and for all $(i,\; j)\; \backslash in\; F\; :\; |X\_i\; \backslash cap\; X\_j|\; =\; k$.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tree decomposition」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.